---
id: 5900f5021000cf542c510015
title: 'Завдання 406: гра на вгадування'
challengeType: 1
forumTopicId: 302074
dashedName: problem-406-guessing-game
---

# --description--

Ми намагаємось знайти невідоме число з множини цілих чисел {1, 2, ..., $n$} за допомогою запитань. На кожне запитання (число) ми отримуємо одну з трьох можливих відповідей:

- «Назване число менше за невідоме число» (і з вас стягується плата a), або
- «Назване число більше за невідоме число» (і з вас стягується плата b), або
- «Так, це воно!» (і гра закінчується).

Враховуючи значення $n$, $a$ та $b$, оптимальна стратегія мінімізує загальну плату <u>в найгіршому можливому випадку</u>.

Наприклад, якщо $n = 5$, $a = 2$ та $b = 3$, то першим названим числом може бути <strong>2</strong>.

Якщо нам кажуть, що 2 більше за невідоме число (з платою $b = 3$), ми будемо впевненими, що <strong>1</strong> є невідомим числом (з загальною платою <strong><span style="color: blue;">3</span></strong>).

Якщо нам кажуть, що 2 менше за невідоме число (з платою $a = 2$), то наступним названим значенням буде <strong>4</strong>.

Якщо нам кажуть, що 4 більше за невідоме число (з платою $b = 3$), ми будемо впевненими, що <strong>3</strong> є невідомим числом (з загальною платою $2 + 3 = \color{blue}{\mathbf{5}}$).

Якщо нам кажуть, що 4 менше за невідоме число (з платою $a = 2$), ми будемо впевненими, що <strong>5</strong> є невідомим числом (з загальною платою $2 + 2 = \color{blue}{\mathbf{4}}$).

Таким чином, найгірша можлива плата цієї стратегії становить <strong><span style="color: red">5</span></strong>. Також можна довести, що це найменша найгірша можлива плата, якої можна досягти. Тому, ми щойно описали оптимальну стратегію для наданих значень $n$, $a$ та $b$.

Нехай $C(n, a, b)$ буде найгіршою можливою платою, визначеною оптимальною стратегією для наданих значень $n$, $a$ та $b$.

Ось декілька прикладів:

$$\begin{align}   & C(5, 2, 3) = 5 \\\\
  & C(500, \sqrt{2}, \sqrt{3}) = 13.220\\,731\\,97\ldots \\\\   & C(20\\,000, 5, 7) = 82 \\\\
  & C(2\\,000\\,000, √5, √7) = 49.637\\,559\\,55\ldots \\\\ \end{align}$$

Нехай $F_k$ буде числами Фібоначчі $F_k = F_{k - 1} + F_{k - 2}$ з початковими значеннями $F_1 = F_2 = 1$.

Знайдіть $\displaystyle\sum_{k = 1}^{30} C({10}^{12}, \sqrt{k}, \sqrt{F_k})$ та дайте відповідь, заокруглену до восьми знаків після коми.

# --hints--

`guessingGame()` має повернути `36813.12757207`.

```js
assert.strictEqual(guessingGame(), 36813.12757207);
```

# --seed--

## --seed-contents--

```js
function guessingGame() {

  return true;
}

guessingGame();
```

# --solutions--

```js
// solution required
```
